package sort;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @Author: yuisama
 * @Date: 2021/9/14 10:56
 * @Description:七大排序算法的实现
 * 默认排序后的集合都是升序排列
 */
public class SevenSortImpl {
    /**
     * 选择排序
     * 算法的核心思想
     * 每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），
     * 直到全部待排序的数据元素排完 。
     * @param arr
     */
    public static void selectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            // 有序区间[0,i]
            int min = i;
            // 无序区间 [i+1...n)
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            swap(arr,i,min);
        }
    }

    // 双向选择排序
    // 每次从无序区间内选出最小值放在无序区间最前面，从无序区间选出最大值放在无序区间最后面
    public static void selectionSortOP(int[] arr) {
        int low = 0,high = arr.length - 1;
        while (low <= high) {
            int min = low;
            int max = low;
            for (int i = low + 1; i <= high; i++) {
                if (arr[i] > arr[max]) {
                    max = i;
                }
                if (arr[i] < arr[min]) {
                    min = i;
                }
            }
            swap(arr,low,min);
            if (max == low) {
                // 此时最大值已经被换到min的位置
                max = min;
            }
            swap(arr,max,high);
            // 更新两个引用，现在low和high对应的已经是最终元素
            low += 1;
            high -= 1;
        }
    }

    /**
     * 基础插入排序，思想与扑克牌整理思想类似
     * 将待排序集合分为已处理好的元素集(i = 0)与待处理的元素集[i+1..n]
     * 每次循环都在查找arr[i]元素适合的插入位置
     * 与选择排序最大的不同在于，插入排序的第二层循环可以提前结束
     * @param arr
     */
    public static void insertSortBase(int[] arr) {
        // 已排序集合[0,i)
        // 无序区间[i,n)
        // 每次选择无序区间的第一个元素插入到有序区间的合适位置
        // 默认arr[0]已经有序，因此从1开始
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

    /**
     * 二分法找到有序区间待插入位置
     * @param arr
     */
    public static void bsInsertionSort(int[] arr) {
        // 有序区间[0,i)
        for (int i = 1; i < arr.length; i++) {
            int val = arr[i];
            int left = 0;
            int right = i;
            while (left < right) {
                int m = left + ((right - left) >> 1);
                // 等于的情况放在左半区间，保证稳定性
                if (val >= arr[m]) {
                    left = m + 1;
                }else {
                    right = m;
                }
            }
            // 数据搬移
            for (int j = i; j > left; j--) {
                arr[j] = arr[j - 1];
            }
            // 此时left就是待插入位置
            arr[left] = val;
        }
    }

    /**
     * 对于给定的数组arr，在[l...r]区间上使用插入排序
     * 该函数用做O(NlogN)级别排序函数的子过程
     * @param arr
     * @param l
     * @param r
     */
    private static void insertSort(int[] arr,int l,int r) {
        // 在[l..r]上进行插入排序，默认arr[l..i)为处理过的数据
        // [i...r]为未处理过的数据
        for (int i = l + 1; i <= r; i++) {
            for (int j = i; j > l && arr[j] < arr[j - 1]; j--) {
                swap(arr,j,j - 1);
            }
        }
    }

    /**
     * 希尔排序，每次gap /= 2
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int gap = arr.length >> 1;
        while (gap > 1) {
            insertSortGap(arr,gap);
            gap = gap >> 1;
        }
        // 全集合上插入排序
        insertSortGap(arr,1);
    }

    /**
     * 按照gap将arr分为若干个组进行插入排序
     * @param arr
     * @param gap
     */
        private static void insertSortGap(int[] arr, int gap) {
        for (int i = gap; i < arr.length; i++) {
            // 距离都为gap的分为一组进行插入排序
            // 此时要不断向前判断，不能向后判断
            for (int j = i; j - gap >= 0 && arr[j] < arr[j - gap]; j -= gap) {
                swap(arr,j,j - gap);
            }
        }
    }

    /**
     * 冒泡排序
     * 相邻两个元素比较，小的换前面，大的换后面，每次循环都把最"重"的元素放在最后面
     * @param arr
     */
    public static void bubbleSort(int[] arr) {
        // 这里i的最大值不能超过n-1，因为向后看相邻元素
        for (int i = 0; i < arr.length - 1; i++) {
            // 若走完一个子过程发现没有元素交换，则此时集合已经有序，无需再次循环
            boolean isSorted = true;
            // 每次走完一个子循环，当前最大的元素已经处在最终位置
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr,j,j + 1);
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }

    private static void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void mergeSort(int[] arr) {
        mergeSortInternal(arr,0,arr.length - 1);
    }

    /**
     * 自底向上的归并排序
     * @param arr 要排序的数组
     */
    public static void mergeSortNonRecursion(int[] arr) {
        // 最外层循环表示每次merge的元素个数，最开始1个，第二次两个，第三次4个，直到整个数组的merge
        for (int sz = 1; sz <= arr.length; sz += sz) {
            // 最内层循环表示每次merge开始的起始索引
            // i + sz < n表示还有右半区间
            for (int i = 0; i + sz < arr.length; i += sz + sz) {
                // 右区间取i + 2 * sz - 1与arr.length - 1的最小值因为有可能右半区间长度不足 sz / 2
                // 此时取整个数组长度即可。
                merge(arr,i,i + sz - 1,Math.min(i + sz + sz - 1,arr.length - 1));
            }
        }
    }

    /**
     * 快速排序
     * @param arr
     */
    public static void quickSort(int[] arr) {
        quickSortInternal(arr,0,arr.length - 1);
    }

    // 快排的非递归写法
    public static void quickSortNonRecursion(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(arr.length - 1);
        stack.push(0);
        // 栈中存放了每一个待排序的区间
        while (!stack.isEmpty()) {
            int left = stack.pop();
            int right = stack.pop();
            if (left >= right) {
                continue;
            }
            int p = partition(arr,left,right);
            // 继续入栈两个子区间
            stack.push(p - 1);
            stack.push(left);

            stack.push(right);
            stack.push(p + 1);
        }
    }

    /**
     * 双路快速排序
     * 解决待排序集合中大量重复元素
     * @param arr
     */
    public static void quickSort2(int[] arr) {
        quickSortInternal2(arr,0,arr.length - 1);
    }

    /**
     * 三路快排
     * 在一次操作中将所有重复元素一次放在最终位置
     * 最后只需要递归的在小于和大于v的子区间快排即可
     * @param arr
     */
    public static void quickSort3(int[] arr) {
        quickSortInternal3(arr,0,arr.length - 1);
    }

    public static void jdkQuickSort(int[] arr) {
        Arrays.sort(arr);
    }

    public static void quickSortHoare(int[] arr) {
        quickSortHoareInternal(arr,0,arr.length - 1);
    }


    private static void quickSortHoareInternal(int[] arr, int left, int right) {
        if (right - left <= 15) {
            insertSort(arr,left,right);
            return;
        }
        int partition = partitionHoare(arr,left,right);
        quickSortHoareInternal(arr,left,partition - 1);
        quickSortHoareInternal(arr,partition + 1,right);
    }
    /**
     * Hoare挖坑分区
     * @param arr
     * @param left
     * @param right
     */
    private static int partitionHoare(int[] arr, int left, int right) {
        int i = left;
        int j = right;
        int randomIndex = (int) (Math.random() * (right - left + 1)) + left;
        swap(arr,left,randomIndex);
        int pivot = arr[left];
        while (i < j) {
            // 先从后向前找到第一个 < p的停止
            while (i < j && arr[j] >= pivot) {
                j --;
            }
            // 小的元素填坑到i
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot) {
                i ++;
            }
            // 大的元素填坑到j
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        return i;
    }

    /**
     * 三路快排
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal3(int[] arr, int l, int r) {
        if (r - l <= 15) {
            insertSort(arr,l,r);
            return;
        }
        int randomIndex = (int) (Math.random() * (r - l + 1)) + l;
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1...lt] < v
        int lt = l;
        // arr[gt...r] > v
        int gt = r + 1;
        // arr[lt + 1..i) == v,i指向当前要处理的元素
        int i = l + 1;
        // 终止条件i和gt重合
        while (i < gt) {
            if (arr[i] < v) {
                swap(arr,lt + 1,i);
                lt ++;
                i ++;
            }else if (arr[i] > v) {
                // 此时不需要i++，因为gt-1这个未处理的元素换到i位置
                swap(arr,gt - 1,i);
                gt --;
            }else {
                // 此处arr[i] == v
                i ++;
            }
        }
        swap(arr,l,lt);
        // 交换后arr[l..lt - 1] < v ; arr[gt..r] >v
        quickSortInternal3(arr,l,lt - 1);
        quickSortInternal3(arr,gt,r);
    }

    /**
     * 二路快排
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal2(int[] arr, int l, int r) {
        if (r - l <= 15) {
            insertSort(arr,l,r);
            return;
        }
        int p = partition2(arr,l,r);
        quickSortInternal2(arr,l,p - 1);
        quickSortInternal2(arr,p + 1,r);
    }

    /**
     * 二路快排partition分区算法
     * i从前向后扫描碰到第一个>=v的元素停止
     * j从后向前扫描碰到第一个<=v的元素停止
     * swap(i,j)
     * 此时可以保证等于v的元素被交换到左右两个子区间，避免了单个区间过大或过小的算法退化
     * @param arr
     * @param l
     * @param r
     * @return
     */
    private static int partition2(int[] arr, int l, int r) {
        int randomIndex = (int) (Math.random() * (r - l + 1)) + l;
        swap(arr,l,randomIndex);
        int v = arr[l];
        // arr[l + 1..i) <= v <= arr(j..r]
        int i = l + 1,j = r;
        while (true) {
            // 1.i的合法性
            // 2.i从前向后扫描碰到第一个 >= v的元素停止
            while (i <= r && arr[i] < v) {
                i ++;
            }
            // j从后向前扫描碰到第一个 <= v 的元素停止
            while (j >= l + 1 && arr[j] > v) {
                j --;
            }
            if (i > j) {
                // 集合扫描完毕
                break;
            }
            swap(arr,i,j);
            i ++;
            j --;
        }
        // 扫描完毕，j落在最后一个 <= v的元素位置，交换l与j的元素，返回j的索引
        swap(arr,l,j);
        return j;
    }

    /**
     * 在arr[l..r]上进行快速排序
     * @param arr
     * @param l
     * @param r
     */
    private static void quickSortInternal(int[] arr, int l, int r) {
        if (r - l <= 15) {
            // 小数组用插入优化
            insertSort(arr,l,r);
            return;
        }
        int p = partition(arr,l,r);
        // 继续在左右两个区间进行快速排序
        quickSortInternal(arr,l,p - 1);
        quickSortInternal(arr,p + 1,r);
    }

    /**
     * 第一版实现
     * 随机化分区
     * 对arr[l..r]进行partition操作
     * @param arr
     * @param l
     * @param r
     * @return 返回p索引，使得arr[l..p - 1]<arr[p]<arr[p + 1..r]
     */
    private static int partition(int[] arr, int l, int r) {
        // 随机选择一个数组元素作为基准值，处理在近乎有序数组中的退化问题
        int randomIndex = (int) (Math.random() * (r - l + 1)) + l;
        swap(arr,l,randomIndex);
        int v = arr[l];
        int j = l;
        // arr[l + 1...j] < v < arr[j + 1..i - 1]
        for (int i = l + 1; i <= r; i++) {
            if (arr[i] < v) {
                // swap(arr,++j,i);
                swap(arr,j + 1,i);
                j ++;
            }
        }
        // 此时循环走完
        // arr[l + 1..j] < v < arr[j + 1...r]
        swap(arr,l,j);
        return j;
    }

    /**
     * 对arr数组在[i..j]区间使用归并排序
     * @param arr 要排序的数组
     * @param i 区间开始索引
     * @param j 区间结束索引
     */
    private static void mergeSortInternal(int[] arr, int i, int j) {
        // 优化2.若r-l<=15,使用插入排序优化
        if (j - i <= 15) {
            insertSort(arr,i,j);
            return;
        }
        int mid = (i + j) / 2;
        // 将原先区间二分，将两个子区间使用归并排序排好序
        mergeSortInternal(arr,i,mid);
        mergeSortInternal(arr,mid + 1,j);
        // 优化1.若此时arr[mid] <= arr[mid + 1],则此时整个数组已经有序，无需再merge
        // 因为在递归的归并排序后，两个子数组arr[i..mid],arr[mid + 1..j]已经有序
        if (arr[mid] > arr[mid + 1]) {
            merge(arr,i,mid,j);
        }
    }

    /**
     * 将arr的两个子数组[l..mid] 与 [mid + 1 .. r]合并
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    private static void merge(int[] arr, int l, int mid, int r) {
        // 开辟一个与原数组大小完全一致的临时数组temp
        // 因为合并区间是左闭右闭区间，因此数组大小为r - l + 1
        int[] temp = new int[r - l + 1];
        // 将原数组的值复制到temp中
        for (int i = l; i <= r; i++) {
            temp[i - l] = arr[i];
        }
        // 遍历两个子数组，取较小值放入arr中
        // 原地修改arr
        int i = l,j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                // 左区间为空
                arr[k] = temp[j - l];
                j ++;
            }else if (j > r) {
                // 右区间为空
                arr[k] = temp[i - l];
                i ++;
            }else if (temp[i - l] <= temp[j - l]) {
                // 相等放在左区间，保证有序性
                arr[k] = temp[i - l];
                i ++;
            }else {
                arr[k] = temp[j - l];
                j ++;
            }
        }
    }

    /**
     * 原地堆排序
     * @param arr 要排序的数组
     */
    public static void heapSort(int[] arr) {
        // 从最后一个非叶子节点开始siftDown，将整个数组调整为最大堆
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            siftDown(arr,i,arr.length);
        }
        // 堆顶元素就是最大值，依次交换最大值到数组末尾然后再调整为堆
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr,0,i);
            siftDown(arr,0,i);
        }
    }

    /**
     * 将arr数组第i个索引的元素下沉，使其满足大堆的性质
     * @param arr
     * @param i
     * @param n 数组元素个数
     */
    private static void siftDown(int[] arr, int i,int n) {
        // 只要还有左孩子
        while ((2 * i + 1) < n) {
            int j = 2 * i + 1;
            // 还有右孩子且右孩子的值大于左孩子
            if (j + 1 < n && arr[j + 1] > arr[j]) {
                j ++;
            }
            // 此时j存储了左右孩子最大值
            if (arr[i] >= arr[j]) {
                break;
            }else {
                swap(arr,i,j);
                // 继续向下判断
                i = j;
            }
        }
    }

    public static void main(String[] args) throws Exception{
        int[] arr = SortHelper.generateRandomArray(1000000,0,100);
        int[] arrCopy = SortHelper.arrayCopy(arr);
        int[] arrCopy1 = SortHelper.arrayCopy(arr);
        int[] arrCopy2 = SortHelper.arrayCopy(arr);
        int[] arrCopy3 = SortHelper.arrayCopy(arr);
        int[] arrCopy4 = SortHelper.arrayCopy(arr);
        SortHelper.testSort("quickSort2",arr);
        SortHelper.testSort("quickSortHoare",arrCopy4);
        SortHelper.testSort("mergeSort",arrCopy3);
        SortHelper.testSort("heapSort",arrCopy1);
//        SortHelper.testSort("insertSortBase",arrCopy);
//        SortHelper.testSort("bsInsertionSort",arrCopy1);
//        SortHelper.testSort("shellSort",arrCopy2);
//        int[] arr = {6,1,2,7,9,3,4,5,10,8};
//        quickSortHoare(arr);
//        System.out.println(Arrays.toString(arr));
    }
}
